home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 09 - 1993 / 09.04 Apr 93 / Programmers' Challenge / Descramble.c
Encoding:
C/C++ Source or Header  |  1994-11-06  |  5.9 KB  |  203 lines  |  [TEXT/KAHL]
  1. #include <stdlib.h>
  2. #include <string.h>
  3.  
  4. /****************************************************/
  5. /* Descramble.c:                                    */                             
  6. /*   A procedure that returns a smooth transition    */
  7. /*     from one string to another with the same        */
  8. /*     characters, but in a different order.            */
  9. /* Author: Jeremy Vineyard                            */
  10. /*                                                    */
  11. /* Includes: <stdLib.h>, <string.h>                    */
  12. /****************************************************/
  13.  
  14. void Descramble(
  15.     Str255            startString,
  16.     Str255            endString,
  17.     unsigned short    numSteps,
  18.     Str255            *stepStringPtrs[20] )
  19. {
  20.     short        i, j, k;
  21.     short        strLength = startString[0];
  22.     div_t        divResult;
  23.     short        destination, memSwitch;
  24.     Boolean        switchPossible;
  25.  
  26.     short        distances[256];
  27.     short        destMap[256];
  28.     Boolean        destSwitchMap[256];
  29.     Boolean        checkList[256];
  30.     
  31.     /* Clear the destination switching map for use. */
  32.     /* Only clear it up to strLength to save time.  */
  33.     for (i = 1; i <= strLength; i++)
  34.         destSwitchMap[i] = false;
  35.         
  36.     /* This loop searches for a duplicate char 'j' for the char 'i'.   */
  37.     /* Once it finds a duplicate, it checks to see whether it is        */
  38.     /* already being used as another char's destination. If not, it    */
  39.     /* shows that char 'j' is char 'i's destination, sets the destMap  */
  40.     /* to show that char 'j' is being used, and calculates how far the */
  41.     /* char 'i' needs to travel on each step to get to its destination.*/
  42.     for (i = 1; i <= strLength; i++)
  43.         for (j = 1; j <= strLength; j++)
  44.             if ( startString[i] == endString[j] && ! destSwitchMap[j] )
  45.             {
  46.                 /* If destSwitchMap[j] is set, then it already has */
  47.                 /* a char which is using it for a destination.     */
  48.                 destSwitchMap[j] = true;
  49.                 
  50.                 /* Remember this char's destination. */
  51.                 destMap[i] = j;
  52.                 
  53.                 /* Find out how far this char should move on each step.       */
  54.                 if (i == j)
  55.                     distances[i] = 0;
  56.                 else
  57.                 {
  58.                    divResult = div(j - i, numSteps);
  59.                    distances[i] = divResult.quot;
  60.                 
  61.                    /* Use the remainder to make sure this char moves each step. */ 
  62.                    if (divResult.rem != 0)
  63.                        if (divResult.rem < 0)
  64.                           distances[i] -= 1;
  65.                        else
  66.                           distances[i] += 1;
  67.                     
  68.                    /* Increment to exit this loop. */
  69.                    j = 512;
  70.                 }
  71.             }
  72.                         
  73.     /* In this loop, each character tries to move towards  */
  74.     /* its destination. Its distance is then recalculated  */
  75.     /* to compensate for it being switched.                */
  76.     /* This creates a 'morphing' effect, where the letters */
  77.     /* in the start string gradually change into their     */
  78.     /* positions in the end string.                           */
  79.     for (i = 0; i < numSteps; i++)
  80.     {
  81.         /* Copy the appropriate string for switching. */
  82.         if (i > 0)
  83.             memcpy(*stepStringPtrs[i], *stepStringPtrs[i - 1], strLength + 1);
  84.         else
  85.             memcpy(*stepStringPtrs[0], startString, strLength + 1);
  86.         
  87.         /* Clear the check list for use. */
  88.         for (k = 1; k <= strLength; k++)
  89.             checkList[k] = false;
  90.             
  91.         /* This loop switches characters until switchPossible = false. */        
  92.         do
  93.         {
  94.          switchPossible = false;
  95.  
  96.          for (j = 1; j <= strLength; j++)
  97.          {
  98.              if (distances[j] != 0 && ! checkList[j])
  99.              {
  100.                 /* Calculate this char's intended destination for this step. */
  101.                 destination = j + distances[j];
  102.                     
  103.                 if (checkList[destination])
  104.                 {
  105.                       /* If the destination has already been used, */
  106.                       /* find the nearest one to it to switch to.  */
  107.                       destination = -1;
  108.                       
  109.                    if (distances[j] > 0)
  110.                        for (k = destination - 1; k > j; k -= 1)
  111.                            if (! checkList[k] && distances[k] != 0)
  112.                            {
  113.                                destination = k;
  114.                                k = 512;
  115.                            }
  116.                            else;
  117.                    else
  118.                        for (k = destination + 1; k < j; k++)
  119.                            if (! checkList[k] && distances[k] != 0)
  120.                            {
  121.                                destination = k;
  122.                                k = 512;
  123.                            }
  124.                 }
  125.                 
  126.                 if (destination > 0)
  127.                 {
  128.                    /* If destination is a valid number, */
  129.                    /* Do the neccessary switching.       */
  130.                    
  131.                   /* Switch the characters in the string */
  132.                   memSwitch = stepStringPtrs[i][0][destination];
  133.                   stepStringPtrs[i][0][destination] = stepStringPtrs[i][0][j];
  134.                   stepStringPtrs[i][0][j] = memSwitch;
  135.                   
  136.                   /* Switch the character's mapped destinations.  */
  137.                   memSwitch = destMap[destination];
  138.                   destMap[destination] = destMap[j];
  139.                   destMap[j] = memSwitch;
  140.                   
  141.                   /* Show that the destination has been switched. */
  142.                   checkList[destination] = true;
  143.                   
  144.                   /* Recalculate the switched char's distance.    */
  145.                   if (destMap[j] == j)
  146.                       distances[j] = 0;
  147.                   else if (i + 1 < numSteps)
  148.                   {
  149.                      divResult = div(destMap[j] - j, numSteps - i - 1);
  150.                     distances[j] = divResult.quot;
  151.                     if (divResult.rem != 0)
  152.                         if (divResult.rem < 0)
  153.                              distances[j] -= 1;
  154.                         else
  155.                             distances[j] += 1;
  156.                  }
  157.                  
  158.                   switchPossible = true;
  159.                 }
  160.               }
  161.           }
  162.         } while (switchPossible);
  163.         
  164.         if (i + 1 == numSteps)
  165.             return;
  166.             
  167.         /* Recalculate all distances to compensate for switched char's. */
  168.         for (k = 1; k <= strLength; k++)
  169.             if (distances[k] != 0)
  170.             {
  171.                 if (destMap[k] == k)
  172.                     distances[k] = 0;
  173.                 else if (i + 1 < numSteps)
  174.                 {
  175.                    /* Recalculate how far this char needs to move */
  176.                    /* with the number of steps that are left.     */
  177.                    divResult = div(destMap[k] - k, numSteps - i - 1);
  178.                    distances[k] = divResult.quot;
  179.                    if (divResult.rem != 0)
  180.                        if (divResult.rem < 0)
  181.                            distances[k] -= 1;
  182.                        else
  183.                            distances[k] += 1;
  184.                 }
  185.             }
  186.     }
  187. }
  188.  
  189. main()
  190. {
  191.     short        i;
  192.     Str255        *stepStrings[20];
  193.  
  194.     /* VERY IMPORTANT:                               */
  195.     /*     If stepStrings[x] are not allocated with */
  196.     /*      a call to malloc, then they will have   */
  197.     /*     null values!!                              */
  198.     for (i = 0; i < 20; i++)
  199.         stepStrings[i] = malloc(256);
  200.          
  201.     Descramble("\pFORT RED BORDER", "\pROBERT REDFORD", 4, stepStrings);
  202. }
  203.